/**
 * 输入一个链表,按链表从尾到头的顺序返回一个ArrayList
 *
 */

import java.util.ArrayList;
import java.util.Stack;

/**
 * 思路:
 * 1.stack
 * 2.数组 , 逆序
 * 3.递归
 */
public class suanfa06 {
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        if (listNode == null) {
            return list;
        }
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }

    public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        printListFromTailToHeadHelper(listNode, list);
        return list;
    }

    private void printListFromTailToHeadHelper(ListNode listNode, ArrayList<Integer> list) {
        if (listNode == null) {
            return;
        }
        printListFromTailToHeadHelper(listNode.next,list);
        list.add(listNode.val);
    }

}
